package com.example.recall31;

import org.springframework.util.CollectionUtils;

import java.util.Arrays;
import java.util.List;

/**
 * @description 0-1背包问题，0 不放入背包，1 放入背包
 * @auther lijiewei
 * @date 2022/2/9 15:42
 */
public class Knapsack01 {

    //存储背包中物品总重量的最大值
    private int maxW = Integer.MIN_VALUE;

    private int[] result = new int[]{};

    /**
     * 石头放入背包
     * @param i 考察到那个物品
     * @param cw 已经装进去的物品的重量和
     * @param items 每个物品的重量
     * @param n 物品个数
     * @param w 背包能装的重量
     * @return
     * @author lijiewei
     * @date   2022/2/9 15:49
     */
    public void f(int i, int cw, int[] items, int n, int w) {
        if (i < n) {
            result[i] = 0;
        }

        //背包已经装满，或者考察完了所有物品
        if (cw == w || i == n) {
            if (cw > maxW) {
                maxW = cw;
            }
            for (int i1 = 0; i1 < result.length; i1++) {
                System.out.print(result[i1] + "");
            }
            System.out.println();
            return;
        }
        //先判断下一个物品
        f(i+1, cw, items, n, w);
        //已经超过背包承受的重量时，不再装
        if (cw + items[i] <=w) {
            result[i] = 1;
            f(i+1, cw+items[i], items, n, w);
        }
    }


    public void setResult(int[] result) {
        this.result = result;
    }
}
